#include <bits/stdc++.h>
using namespace std;



class Solution
{
public:
    // int dfs(int target, vector<int> & nums, vector<int> &mem)
    // {
    //     if (target == 0)
    //     {
    //         return 1;
    //     }
    //     if (mem[target] != -1){
    //         return mem[target];
    //     }
    //     int ans = 0;
    //     for (int i = 0; i < nums.size(); i++)
    //     {
    //         if (target >= nums[i])
    //             ans += dfs(target - nums[i], nums, mem);
    //     }
    //     return mem[target]  = ans;
    // }
    int combinationSum4(vector<int>& nums, int target)
    {
        // vector<int> mem(target + 1, -1);
        vector<size_t> dp(target + 1, 0);
        dp[0]  = 1;
        for (int i = 1; i <= target; i++)
        { 
            for (int j = 0; j < nums.size(); j++)
            { 
                if (i >= nums[j])
                    dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
};